#include "knapsack.h"

// Utility function to generate random items
void generateItems(Item* items, int n) {
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        items[i].id = i + 1;
        items[i].weight = 1 + (rand() % 100);  // Random weight between 1-100
        items[i].value = 100 + ((double)rand() / RAND_MAX) * 900;  // Random value between 100-1000
    }
}

// Utility function to print solution
void printSolution(Solution* sol, Item* items, int n) {
    if (!sol) {
        printf("No solution found!\n");
        return;
    }
    
    printf("Selected items:\n");
    printf("ID\tWeight\tValue\n");
    for (int i = 0; i < n; i++) {
        if (sol->selected[i]) {
            printf("%d\t%.2f\t%.2f\n", items[i].id, items[i].weight, items[i].value);
        }
    }
    printf("Total value: %.2f\n", sol->total_value);
    printf("Total weight: %.2f\n", sol->total_weight);
}

// Utility function to free solution memory
void freeSolution(Solution* sol) {
    if (sol) {
        free(sol->selected);
        free(sol);
    }
}

// Brute Force implementation
void bruteForceRecursive(Item* items, int n, double capacity, int* current, int index,
                        Solution* best_sol, double current_value, double current_weight) {
    if (index == n) {
        if (current_value > best_sol->total_value) {
            best_sol->total_value = current_value;
            best_sol->total_weight = current_weight;
            memcpy(best_sol->selected, current, n * sizeof(int));
        }
        return;
    }

    // Don't take current item
    current[index] = 0;
    bruteForceRecursive(items, n, capacity, current, index + 1,
                        best_sol, current_value, current_weight);

    // Take current item if possible
    if (current_weight + items[index].weight <= capacity) {
        current[index] = 1;
        bruteForceRecursive(items, n, capacity, current, index + 1,
                           best_sol, current_value + items[index].value,
                           current_weight + items[index].weight);
    }
}

Solution* bruteForce(Item* items, int n, double capacity) {
    Solution* sol = (Solution*)malloc(sizeof(Solution));
    sol->selected = (int*)calloc(n, sizeof(int));
    sol->total_value = 0;
    sol->total_weight = 0;

    int* current = (int*)calloc(n, sizeof(int));
    bruteForceRecursive(items, n, capacity, current, 0, sol, 0, 0);
    free(current);

    return sol;
}

// Dynamic Programming implementation
Solution* dynamicProgramming(Item* items, int n, double capacity) {
    int W = (int)capacity;
    double** dp = (double**)malloc((n + 1) * sizeof(double*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (double*)calloc(W + 1, sizeof(double));
    }

    // Fill dp table
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (items[i-1].weight <= w) {
                double val_with_item = items[i-1].value + dp[i-1][(int)(w - items[i-1].weight)];
                dp[i][w] = (val_with_item > dp[i-1][w]) ? val_with_item : dp[i-1][w];
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }

    // Construct solution
    Solution* sol = (Solution*)malloc(sizeof(Solution));
    sol->selected = (int*)calloc(n, sizeof(int));
    sol->total_value = dp[n][W];
    sol->total_weight = 0;

    // Backtrack to find selected items
    int w = W;
    for (int i = n; i > 0; i--) {
        if (dp[i][w] != dp[i-1][w]) {
            sol->selected[i-1] = 1;
            w -= (int)items[i-1].weight;
            sol->total_weight += items[i-1].weight;
        }
    }

    // Free dp table
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);

    return sol;
}

// Greedy implementation
Solution* greedy(Item* items, int n, double capacity) {
    // Calculate value per weight ratio
    typedef struct {
        int index;
        double ratio;
    } ItemRatio;

    ItemRatio* ratios = (ItemRatio*)malloc(n * sizeof(ItemRatio));
    for (int i = 0; i < n; i++) {
        ratios[i].index = i;
        ratios[i].ratio = items[i].value / items[i].weight;
    }

    // Sort by ratio (descending)
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (ratios[j].ratio < ratios[j + 1].ratio) {
                ItemRatio temp = ratios[j];
                ratios[j] = ratios[j + 1];
                ratios[j + 1] = temp;
            }
        }
    }

    Solution* sol = (Solution*)malloc(sizeof(Solution));
    sol->selected = (int*)calloc(n, sizeof(int));
    sol->total_value = 0;
    sol->total_weight = 0;

    // Take items in order of ratio until capacity is reached
    double remaining_capacity = capacity;
    for (int i = 0; i < n; i++) {
        int idx = ratios[i].index;
        if (items[idx].weight <= remaining_capacity) {
            sol->selected[idx] = 1;
            sol->total_value += items[idx].value;
            sol->total_weight += items[idx].weight;
            remaining_capacity -= items[idx].weight;
        }
    }

    free(ratios);
    return sol;
}

// Backtracking implementation
void backtrackingRecursive(Item* items, int n, double capacity,
                          int index, double current_value, double current_weight,
                          int* current, Solution* best_sol) {
    // Base case: reached end of items
    if (index == n) {
        if (current_value > best_sol->total_value) {
            best_sol->total_value = current_value;
            best_sol->total_weight = current_weight;
            memcpy(best_sol->selected, current, n * sizeof(int));
        }
        return;
    }

    // Pruning: if remaining capacity is negative, backtrack
    if (current_weight > capacity) return;

    // Include current item
    current[index] = 1;
    backtrackingRecursive(items, n, capacity, index + 1,
                         current_value + items[index].value,
                         current_weight + items[index].weight,
                         current, best_sol);

    // Exclude current item
    current[index] = 0;
    backtrackingRecursive(items, n, capacity, index + 1,
                         current_value, current_weight,
                         current, best_sol);
}

Solution* backtracking(Item* items, int n, double capacity) {
    Solution* sol = (Solution*)malloc(sizeof(Solution));
    sol->selected = (int*)calloc(n, sizeof(int));
    sol->total_value = 0;
    sol->total_weight = 0;

    int* current = (int*)calloc(n, sizeof(int));
    backtrackingRecursive(items, n, capacity, 0, 0, 0, current, sol);
    free(current);

    return sol;
}

// Utility function to write execution time to file
void writeExecutionTime(const char* algorithm, int n, double capacity, double time_ms) {
    char filename[100];
    sprintf(filename, "%s_run_time.txt", algorithm);
    FILE* fp = fopen(filename, "a");
    if (fp) {
        fprintf(fp, "Items: %d, Capacity: %.0f, Time: %.2f ms\n", n, capacity, time_ms);
        fclose(fp);
    }
}

// Utility function to write fake code
void writeFakeCode(const char* algorithm) {
    char filename[100];
    sprintf(filename, "%s_fakecode.txt", algorithm);
    FILE* fp = fopen(filename, "w");
    if (fp) {
        if (strcmp(algorithm, "bruteforce") == 0) {
            fprintf(fp, "Brute Force Algorithm Pseudocode:\n\n");
            fprintf(fp, "function bruteForce(items, n, capacity):\n");
            fprintf(fp, "    best_value = 0\n");
            fprintf(fp, "    best_solution = null\n");
            fprintf(fp, "    for each possible combination of items:\n");
            fprintf(fp, "        if total_weight <= capacity and total_value > best_value:\n");
            fprintf(fp, "            best_value = total_value\n");
            fprintf(fp, "            best_solution = current_combination\n");
            fprintf(fp, "    return best_solution\n");
        }
        else if (strcmp(algorithm, "dynamic") == 0) {
            fprintf(fp, "Dynamic Programming Algorithm Pseudocode:\n\n");
            fprintf(fp, "function dynamicProgramming(items, n, capacity):\n");
            fprintf(fp, "    create table dp[n+1][capacity+1]\n");
            fprintf(fp, "    for i from 0 to n:\n");
            fprintf(fp, "        for w from 0 to capacity:\n");
            fprintf(fp, "            if item[i] weight <= w:\n");
            fprintf(fp, "                dp[i][w] = max(value[i] + dp[i-1][w-weight[i]], dp[i-1][w])\n");
            fprintf(fp, "            else:\n");
            fprintf(fp, "                dp[i][w] = dp[i-1][w]\n");
            fprintf(fp, "    return reconstruct_solution(dp)\n");
        }
        else if (strcmp(algorithm, "greedy") == 0) {
            fprintf(fp, "Greedy Algorithm Pseudocode:\n\n");
            fprintf(fp, "function greedy(items, n, capacity):\n");
            fprintf(fp, "    calculate value/weight ratio for each item\n");
            fprintf(fp, "    sort items by ratio in descending order\n");
            fprintf(fp, "    for each item in sorted order:\n");
            fprintf(fp, "        if item fits in remaining capacity:\n");
            fprintf(fp, "            add item to solution\n");
            fprintf(fp, "    return solution\n");
        }
        else if (strcmp(algorithm, "backtracking") == 0) {
            fprintf(fp, "Backtracking Algorithm Pseudocode:\n\n");
            fprintf(fp, "function backtracking(items, n, capacity):\n");
            fprintf(fp, "    if n == 0 or capacity <= 0:\n");
            fprintf(fp, "        return 0\n");
            fprintf(fp, "    if weight[n-1] > capacity:\n");
            fprintf(fp, "        return backtracking(items, n-1, capacity)\n");
            fprintf(fp, "    return max(value[n-1] + backtracking(items, n-1, capacity-weight[n-1]),\n");
            fprintf(fp, "               backtracking(items, n-1, capacity))\n");
        }
        fclose(fp);
    }
} 